import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class test {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<Integer>();
        Map<String, Integer> hash1 = new HashMap<String, Integer>();

        for(String str : words) hash1.put(str, hash1.getOrDefault(str,0)+1);

        int len = words[0].length(), m = words.length;

        for(int i = 0; i < len; i++) {
            Map<String, Integer> hash2 = new HashMap<String, Integer>();
            for(int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                //进窗口
                String in = s.substring(right, right+len);
                // words 里含有in
                hash2.put(in, hash2.getOrDefault(in,0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;

                //出窗口
                if(right - left + 1 > len * m) {
                    String out = s.substring(left, left+len);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out, hash2.get(out)-1);
                    left = left + len;
                }


                //判断
                if(count == m)  ret.add(left);

            }
        }
        return ret;
    }


    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = {"foo","bar"};
        List<Integer> list1 = new ArrayList<>();
        list1 = findSubstring(s, words);
        System.out.println(list1);
    }
}
